home *** CD-ROM | disk | FTP | other *** search
/ Nebula 2 / Nebula Two.iso / SourceCode / MiscKit1.7.1 / MiscKit / Palettes / MiscTableScroll / MiscSparseSet.h < prev    next >
Encoding:
C/C++ Source or Header  |  1996-02-11  |  3.0 KB  |  95 lines
  1. #ifndef __MiscSparseSet_h
  2. #define __MiscSparseSet_h
  3. #ifdef __GNUC__
  4. # pragma interface
  5. #endif
  6. //=============================================================================
  7. //
  8. //        Copyright (C) 1995 by Paul S. McCarthy and Eric Sunshine.
  9. //                Written by Paul S. McCarthy and Eric Sunshine.
  10. //                            All Rights Reserved.
  11. //
  12. //        This notice may not be removed from this source code.
  13. //
  14. //        This object is included in the MiscKit by permission from the authors
  15. //        and its use is governed by the MiscKit license, found in the file
  16. //        "License.rtf" in the MiscKit distribution.    Please refer to that file
  17. //        for a list of all applicable permissions and restrictions.
  18. //        
  19. //=============================================================================
  20. //-----------------------------------------------------------------------------
  21. // MiscSparseSet.h
  22. //
  23. //        This object impelements a sparse set.  The set is represented by an
  24. //        array of ranges kept in sorted ascending order.
  25. //
  26. //-----------------------------------------------------------------------------
  27. //-----------------------------------------------------------------------------
  28. // $Id: MiscSparseSet.h,v 1.1 95/09/27 12:21:21 zarnuk Exp $
  29. // $Log:        MiscSparseSet.h,v $
  30. //    Revision 1.1  95/09/27    12:21:21  zarnuk
  31. //    Initial revision
  32. //    
  33. //-----------------------------------------------------------------------------
  34. #include "bool.h"
  35.  
  36. class MiscSparseSet
  37.     {
  38.     public:
  39.         int const INVALID = -1;
  40.  
  41.     private:
  42.         struct Range
  43.             {
  44.             int min_val;
  45.             int max_val;
  46.             };
  47.  
  48.         unsigned int lim;
  49.         unsigned int capacity;
  50.         Range* array;
  51.         int cursor;
  52.  
  53.         void expand( unsigned int new_capacity );
  54.         void expand();
  55.         int bsearch( int x ) const;
  56.         void fixCursor();
  57.         void insertAt( unsigned int, unsigned int lo, unsigned int hi );
  58.         void deleteAt( unsigned int, unsigned int slots );
  59.         int merge( int x, unsigned int at );
  60.         int slice( int x, unsigned int at );
  61.  
  62.     public:
  63.         MiscSparseSet() : lim(0), capacity(0), array(0), cursor(INVALID) {}
  64.         MiscSparseSet( MiscSparseSet const& );
  65.         ~MiscSparseSet();
  66.  
  67.         MiscSparseSet& operator=( MiscSparseSet const& );
  68.         bool operator==( MiscSparseSet const& ) const;
  69.         bool operator!=( MiscSparseSet const& s ) const
  70.                         { return !operator==(s); }
  71.  
  72.         int getCursor() const { return cursor; }
  73.         void setCursor( int c ) { cursor = c; fixCursor(); }
  74.         void clearCursor() { cursor = INVALID; }
  75.  
  76.         bool contains( int x ) const { return (bsearch( x ) >= 0); }
  77.         bool isEmpty() const { return (lim == 0); }
  78.         void empty() { lim = 0; clearCursor(); }
  79.         unsigned int count() const;                        // # elments in set
  80.  
  81.         void add( int low, int high );    // add a range
  82.         void add( int x ) { add( x, x ); }
  83.         void remove( int low, int high );        // remove a range
  84.         void remove( int x ) { remove( x, x ); }
  85.         void toggle( int );
  86.         void shiftUpAt( int x );
  87.         void shiftDownAt( int x );
  88.  
  89.         unsigned int numRanges() const { return lim; }
  90.         void getRangeAt( unsigned int i, int& lo, int& hi ) const;
  91.         void getTotalRange( int& lo, int& hi ) const;
  92.     };
  93.  
  94. #endif // __MiscSparseSet_h
  95.